package com.demo.java.OD1_50.OD38;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【 第 N 个排列】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145559198
 */
public class OdMain {
    private static long[] factorial;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.close();

        // 计算阶乘
        factorial = new long[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        // 初始化序列
        int[] sequence = new int[n];
        for (int i = 0; i < n; i++) sequence[i] = i + 1;

        // 保存结果
        StringBuilder result = new StringBuilder();
        findKthPermutation(n, k, sequence, result);

        // 输出第 k 个排列
        System.out.println(result.toString());
    }

    // 递归求解第 k 个排列
    public static void findKthPermutation(int n, int k, int[] sequence, StringBuilder result) {
        if (n == 0) return;  // 基本结束条件

        // 找到当前数字的位置
        int index = (int) ((k - 1) / factorial[n - 1]);
        result.append(sequence[index]);

        // 更新序列，去掉已选择的数字
        int[] newSequence = new int[n - 1];
        for (int i = 0, j = 0; i < n; i++) {
            if (i != index) {
                newSequence[j++] = sequence[i];
            }
        }

        // 更新 k，并递归求解剩下的排列
        k = (int) ((k - 1) % factorial[n - 1]) + 1;
        findKthPermutation(n - 1, k, newSequence, result);
    }
}